package dfs;
/*
* 机器人的运动范围
*
* 思路跟二叉树的dfs一样, 递归参数是什么? 返回值是什么? 递归终止条件是什么?
* */
public class Offer13movingCount {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited=new boolean[m][n];
        return dfs(0,0,m,n,k,visited);
    }

    private int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
        if(i<0 || i>=m || j<0 || j>=n || visited[i][j] || (i%10)+(i/10)+(j%10)+(j/10)>k){
            return 0;
        }
        visited[i][j]=true;
        int a=dfs(i-1,j,m,n,k,visited);
        int b=dfs(i+1,j,m,n,k,visited);
        int c=dfs(i,j-1,m,n,k,visited);
        int d=dfs(i,j+1,m,n,k,visited);

        return a+b+c+d+1;
    }
}
